package week06

import "math"

// 123. 买卖股票的最佳时机 III
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

func maxProfit(prices []int) int {
	var dp = make([][][]int, len(prices)+1)
	for i := range dp {
		dp[i] = [][]int{[]int{math.MinInt32, math.MinInt32, math.MinInt32}, []int{math.MinInt32, math.MinInt32, math.MinInt32}}
	}
	dp[0][0][0] = 0
	for i := 1; i < len(prices)+1; i++ {
		for j := 0; j <= 1; j++ {
			for k := 0; k <= 2; k++ {
				dp[i][j][k] = dp[i-1][j][k]
				if j == 0 {
					dp[i][0][k] = max(dp[i][0][k], dp[i-1][1][k] + prices[i-1])
				} else if k > 0 {
					dp[i][1][k] = max(dp[i][1][k], dp[i-1][0][k-1] - prices[i-1])
				}
			}
		}
	}
	var ans = 0
	for i := 0; i <= 2; i++ {
		ans = max(ans, dp[len(prices)][0][i])
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}